<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 8.6.9" />
<title>编译原理课程设计报告</title>
<style type="text/css">
/* Shared CSS for AsciiDoc xhtml11 and html5 backends */

/* Default font. */
body {
  font-family: Georgia,serif;
}

/* Title font. */
h1, h2, h3, h4, h5, h6,
div.title, caption.title,
thead, p.table.header,
#toctitle,
#author, #revnumber, #revdate, #revremark,
#footer {
  font-family: Arial,Helvetica,sans-serif;
}

body {
  margin: 1em 5% 1em 5%;
}

a {
  color: blue;
  text-decoration: underline;
}
a:visited {
  color: fuchsia;
}

em {
  font-style: italic;
  color: navy;
}

strong {
  font-weight: bold;
  color: #083194;
}

h1, h2, h3, h4, h5, h6 {
  color: #527bbd;
  margin-top: 1.2em;
  margin-bottom: 0.5em;
  line-height: 1.3;
}

h1, h2, h3 {
  border-bottom: 2px solid silver;
}
h2 {
  padding-top: 0.5em;
}
h3 {
  float: left;
}
h3 + * {
  clear: left;
}
h5 {
  font-size: 1.0em;
}

div.sectionbody {
  margin-left: 0;
}

hr {
  border: 1px solid silver;
}

p {
  margin-top: 0.5em;
  margin-bottom: 0.5em;
}

ul, ol, li > p {
  margin-top: 0;
}
ul > li     { color: #aaa; }
ul > li > * { color: black; }

.monospaced, code, pre {
  font-family: "Courier New", Courier, monospace;
  font-size: inherit;
  color: navy;
  padding: 0;
  margin: 0;
}
pre {
  white-space: pre-wrap;
}

#author {
  color: #527bbd;
  font-weight: bold;
  font-size: 1.1em;
}
#email {
}
#revnumber, #revdate, #revremark {
}

#footer {
  font-size: small;
  border-top: 2px solid silver;
  padding-top: 0.5em;
  margin-top: 4.0em;
}
#footer-text {
  float: left;
  padding-bottom: 0.5em;
}
#footer-badges {
  float: right;
  padding-bottom: 0.5em;
}

#preamble {
  margin-top: 1.5em;
  margin-bottom: 1.5em;
}
div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.admonitionblock {
  margin-top: 2.0em;
  margin-bottom: 2.0em;
  margin-right: 10%;
  color: #606060;
}

div.content { /* Block element content. */
  padding: 0;
}

/* Block element titles. */
div.title, caption.title {
  color: #527bbd;
  font-weight: bold;
  text-align: left;
  margin-top: 1.0em;
  margin-bottom: 0.5em;
}
div.title + * {
  margin-top: 0;
}

td div.title:first-child {
  margin-top: 0.0em;
}
div.content div.title:first-child {
  margin-top: 0.0em;
}
div.content + div.title {
  margin-top: 0.0em;
}

div.sidebarblock > div.content {
  background: #ffffee;
  border: 1px solid #dddddd;
  border-left: 4px solid #f0f0f0;
  padding: 0.5em;
}

div.listingblock > div.content {
  border: 1px solid #dddddd;
  border-left: 5px solid #f0f0f0;
  background: #f8f8f8;
  padding: 0.5em;
}

div.quoteblock, div.verseblock {
  padding-left: 1.0em;
  margin-left: 1.0em;
  margin-right: 10%;
  border-left: 5px solid #f0f0f0;
  color: #888;
}

div.quoteblock > div.attribution {
  padding-top: 0.5em;
  text-align: right;
}

div.verseblock > pre.content {
  font-family: inherit;
  font-size: inherit;
}
div.verseblock > div.attribution {
  padding-top: 0.75em;
  text-align: left;
}
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
div.verseblock + div.attribution {
  text-align: left;
}

div.admonitionblock .icon {
  vertical-align: top;
  font-size: 1.1em;
  font-weight: bold;
  text-decoration: underline;
  color: #527bbd;
  padding-right: 0.5em;
}
div.admonitionblock td.content {
  padding-left: 0.5em;
  border-left: 3px solid #dddddd;
}

div.exampleblock > div.content {
  border-left: 3px solid #dddddd;
  padding-left: 0.5em;
}

div.imageblock div.content { padding-left: 0; }
span.image img { border-style: none; vertical-align: text-bottom; }
a.image:visited { color: white; }

dl {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
dt {
  margin-top: 0.5em;
  margin-bottom: 0;
  font-style: normal;
  color: navy;
}
dd > *:first-child {
  margin-top: 0.1em;
}

ul, ol {
    list-style-position: outside;
}
ol.arabic {
  list-style-type: decimal;
}
ol.loweralpha {
  list-style-type: lower-alpha;
}
ol.upperalpha {
  list-style-type: upper-alpha;
}
ol.lowerroman {
  list-style-type: lower-roman;
}
ol.upperroman {
  list-style-type: upper-roman;
}

div.compact ul, div.compact ol,
div.compact p, div.compact p,
div.compact div, div.compact div {
  margin-top: 0.1em;
  margin-bottom: 0.1em;
}

tfoot {
  font-weight: bold;
}
td > div.verse {
  white-space: pre;
}

div.hdlist {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
div.hdlist tr {
  padding-bottom: 15px;
}
dt.hdlist1.strong, td.hdlist1.strong {
  font-weight: bold;
}
td.hdlist1 {
  vertical-align: top;
  font-style: normal;
  padding-right: 0.8em;
  color: navy;
}
td.hdlist2 {
  vertical-align: top;
}
div.hdlist.compact tr {
  margin: 0;
  padding-bottom: 0;
}

.comment {
  background: yellow;
}

.footnote, .footnoteref {
  font-size: 0.8em;
}

span.footnote, span.footnoteref {
  vertical-align: super;
}

#footnotes {
  margin: 20px 0 20px 0;
  padding: 7px 0 0 0;
}

#footnotes div.footnote {
  margin: 0 0 5px 0;
}

#footnotes hr {
  border: none;
  border-top: 1px solid silver;
  height: 1px;
  text-align: left;
  margin-left: 0;
  width: 20%;
  min-width: 100px;
}

div.colist td {
  padding-right: 0.5em;
  padding-bottom: 0.3em;
  vertical-align: top;
}
div.colist td img {
  margin-top: 0.3em;
}

@media print {
  #footer-badges { display: none; }
}

#toc {
  margin-bottom: 2.5em;
}

#toctitle {
  color: #527bbd;
  font-size: 1.1em;
  font-weight: bold;
  margin-top: 1.0em;
  margin-bottom: 0.1em;
}

div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
  margin-top: 0;
  margin-bottom: 0;
}
div.toclevel2 {
  margin-left: 2em;
  font-size: 0.9em;
}
div.toclevel3 {
  margin-left: 4em;
  font-size: 0.9em;
}
div.toclevel4 {
  margin-left: 6em;
  font-size: 0.9em;
}

span.aqua { color: aqua; }
span.black { color: black; }
span.blue { color: blue; }
span.fuchsia { color: fuchsia; }
span.gray { color: gray; }
span.green { color: green; }
span.lime { color: lime; }
span.maroon { color: maroon; }
span.navy { color: navy; }
span.olive { color: olive; }
span.purple { color: purple; }
span.red { color: red; }
span.silver { color: silver; }
span.teal { color: teal; }
span.white { color: white; }
span.yellow { color: yellow; }

span.aqua-background { background: aqua; }
span.black-background { background: black; }
span.blue-background { background: blue; }
span.fuchsia-background { background: fuchsia; }
span.gray-background { background: gray; }
span.green-background { background: green; }
span.lime-background { background: lime; }
span.maroon-background { background: maroon; }
span.navy-background { background: navy; }
span.olive-background { background: olive; }
span.purple-background { background: purple; }
span.red-background { background: red; }
span.silver-background { background: silver; }
span.teal-background { background: teal; }
span.white-background { background: white; }
span.yellow-background { background: yellow; }

span.big { font-size: 2em; }
span.small { font-size: 0.6em; }

span.underline { text-decoration: underline; }
span.overline { text-decoration: overline; }
span.line-through { text-decoration: line-through; }

div.unbreakable { page-break-inside: avoid; }


/*
 * xhtml11 specific
 *
 * */

div.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.tableblock > table {
  border: 3px solid #527bbd;
}
thead, p.table.header {
  font-weight: bold;
  color: #527bbd;
}
p.table {
  margin-top: 0;
}
/* Because the table frame attribute is overriden by CSS in most browsers. */
div.tableblock > table[frame="void"] {
  border-style: none;
}
div.tableblock > table[frame="hsides"] {
  border-left-style: none;
  border-right-style: none;
}
div.tableblock > table[frame="vsides"] {
  border-top-style: none;
  border-bottom-style: none;
}


/*
 * html5 specific
 *
 * */

table.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
thead, p.tableblock.header {
  font-weight: bold;
  color: #527bbd;
}
p.tableblock {
  margin-top: 0;
}
table.tableblock {
  border-width: 3px;
  border-spacing: 0px;
  border-style: solid;
  border-color: #527bbd;
  border-collapse: collapse;
}
th.tableblock, td.tableblock {
  border-width: 1px;
  padding: 4px;
  border-style: solid;
  border-color: #527bbd;
}

table.tableblock.frame-topbot {
  border-left-style: hidden;
  border-right-style: hidden;
}
table.tableblock.frame-sides {
  border-top-style: hidden;
  border-bottom-style: hidden;
}
table.tableblock.frame-none {
  border-style: hidden;
}

th.tableblock.halign-left, td.tableblock.halign-left {
  text-align: left;
}
th.tableblock.halign-center, td.tableblock.halign-center {
  text-align: center;
}
th.tableblock.halign-right, td.tableblock.halign-right {
  text-align: right;
}

th.tableblock.valign-top, td.tableblock.valign-top {
  vertical-align: top;
}
th.tableblock.valign-middle, td.tableblock.valign-middle {
  vertical-align: middle;
}
th.tableblock.valign-bottom, td.tableblock.valign-bottom {
  vertical-align: bottom;
}


/*
 * manpage specific
 *
 * */

body.manpage h1 {
  padding-top: 0.5em;
  padding-bottom: 0.5em;
  border-top: 2px solid silver;
  border-bottom: 2px solid silver;
}
body.manpage h2 {
  border-style: none;
}
body.manpage div.sectionbody {
  margin-left: 3em;
}

@media print {
  body.manpage div#toc { display: none; }
}


</style>
<script type="text/javascript">
/*<![CDATA[*/
var asciidoc = {  // Namespace.

/////////////////////////////////////////////////////////////////////
// Table Of Contents generator
/////////////////////////////////////////////////////////////////////

/* Author: Mihai Bazon, September 2002
 * http://students.infoiasi.ro/~mishoo
 *
 * Table Of Content generator
 * Version: 0.4
 *
 * Feel free to use this script under the terms of the GNU General Public
 * License, as long as you do not remove or alter this notice.
 */

 /* modified by Troy D. Hanson, September 2006. License: GPL */
 /* modified by Stuart Rackham, 2006, 2009. License: GPL */

// toclevels = 1..4.
toc: function (toclevels) {

  function getText(el) {
    var text = "";
    for (var i = el.firstChild; i != null; i = i.nextSibling) {
      if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
        text += i.data;
      else if (i.firstChild != null)
        text += getText(i);
    }
    return text;
  }

  function TocEntry(el, text, toclevel) {
    this.element = el;
    this.text = text;
    this.toclevel = toclevel;
  }

  function tocEntries(el, toclevels) {
    var result = new Array;
    var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
    // Function that scans the DOM tree for header elements (the DOM2
    // nodeIterator API would be a better technique but not supported by all
    // browsers).
    var iterate = function (el) {
      for (var i = el.firstChild; i != null; i = i.nextSibling) {
        if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
          var mo = re.exec(i.tagName);
          if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
            result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
          }
          iterate(i);
        }
      }
    }
    iterate(el);
    return result;
  }

  var toc = document.getElementById("toc");
  if (!toc) {
    return;
  }

  // Delete existing TOC entries in case we're reloading the TOC.
  var tocEntriesToRemove = [];
  var i;
  for (i = 0; i < toc.childNodes.length; i++) {
    var entry = toc.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div'
     && entry.getAttribute("class")
     && entry.getAttribute("class").match(/^toclevel/))
      tocEntriesToRemove.push(entry);
  }
  for (i = 0; i < tocEntriesToRemove.length; i++) {
    toc.removeChild(tocEntriesToRemove[i]);
  }

  // Rebuild TOC entries.
  var entries = tocEntries(document.getElementById("content"), toclevels);
  for (var i = 0; i < entries.length; ++i) {
    var entry = entries[i];
    if (entry.element.id == "")
      entry.element.id = "_toc_" + i;
    var a = document.createElement("a");
    a.href = "#" + entry.element.id;
    a.appendChild(document.createTextNode(entry.text));
    var div = document.createElement("div");
    div.appendChild(a);
    div.className = "toclevel" + entry.toclevel;
    toc.appendChild(div);
  }
  if (entries.length == 0)
    toc.parentNode.removeChild(toc);
},


/////////////////////////////////////////////////////////////////////
// Footnotes generator
/////////////////////////////////////////////////////////////////////

/* Based on footnote generation code from:
 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 */

footnotes: function () {
  // Delete existing footnote entries in case we're reloading the footnodes.
  var i;
  var noteholder = document.getElementById("footnotes");
  if (!noteholder) {
    return;
  }
  var entriesToRemove = [];
  for (i = 0; i < noteholder.childNodes.length; i++) {
    var entry = noteholder.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
      entriesToRemove.push(entry);
  }
  for (i = 0; i < entriesToRemove.length; i++) {
    noteholder.removeChild(entriesToRemove[i]);
  }

  // Rebuild footnote entries.
  var cont = document.getElementById("content");
  var spans = cont.getElementsByTagName("span");
  var refs = {};
  var n = 0;
  for (i=0; i<spans.length; i++) {
    if (spans[i].className == "footnote") {
      n++;
      var note = spans[i].getAttribute("data-note");
      if (!note) {
        // Use [\s\S] in place of . so multi-line matches work.
        // Because JavaScript has no s (dotall) regex flag.
        note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
        spans[i].innerHTML =
          "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
        spans[i].setAttribute("data-note", note);
      }
      noteholder.innerHTML +=
        "<div class='footnote' id='_footnote_" + n + "'>" +
        "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
        n + "</a>. " + note + "</div>";
      var id =spans[i].getAttribute("id");
      if (id != null) refs["#"+id] = n;
    }
  }
  if (n == 0)
    noteholder.parentNode.removeChild(noteholder);
  else {
    // Process footnoterefs.
    for (i=0; i<spans.length; i++) {
      if (spans[i].className == "footnoteref") {
        var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
        href = href.match(/#.*/)[0];  // Because IE return full URL.
        n = refs[href];
        spans[i].innerHTML =
          "[<a href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
      }
    }
  }
},

install: function(toclevels) {
  var timerId;

  function reinstall() {
    asciidoc.footnotes();
    if (toclevels) {
      asciidoc.toc(toclevels);
    }
  }

  function reinstallAndRemoveTimer() {
    clearInterval(timerId);
    reinstall();
  }

  timerId = setInterval(reinstall, 500);
  if (document.addEventListener)
    document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
  else
    window.onload = reinstallAndRemoveTimer;
}

}
asciidoc.install(2);
/*]]>*/
</script>
</head>
<body class="article">
<div id="header">
<h1>编译原理课程设计报告</h1>
<span id="author">徐旗江</span><br />
<span id="email"><code>&lt;<a href="mailto:ICErupt@126.com">ICErupt@126.com</a>&gt;</code></span><br />
<span id="revdate">学号 913106840320 班级 9131065502</span>
<div id="toc">
  <div id="toctitle">Table of Contents</div>
  <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
</div>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div style="page-break-after:always"></div>
</div>
</div>
<div class="sect1">
<h2 id="_使用说明">使用说明</h2>
<div class="sectionbody">
<div class="paragraph"><p>从文件 <code>3-grammar</code> 读入正规文法，从文件 <code>2-grammar</code> 读入上下文无关文法，
从 <code>input-program</code> 读入程序，这些文件都放在当前目录下，然后运行就可以得到
结果。程序中的一个宏开关 <code>ALL_TOKEN</code> 如果设置成1可以输出所有token表即使
程序不能通过编译。可执行程序就是当前目录下的main。
<code>c++</code> 的编译指令是: <code>clang++ -o main -std=gnu++14 -O3 -Wall -Wextra -march=native main.cc src/pasex.cc src/parse.cc</code>
当然也可以用别的编译器。</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_文法输入规范">文法输入规范</h2>
<div class="sectionbody">
<div class="paragraph"><p>项目的测试语言是<a href="https://www.cs.helsinki.fi/u/vihavain/k06/okk/items/minipascalsyntax.html">minipas</a>,
虽然使用minipas进行测试，但是项目本身不局限于具体的语言。minipas的递归下降语法以及词法的BNF定义在
上面的链接里。我们将其翻译成了相应的上下文无关文法以及正规文法作为程序(词法析器和语法分析器)的输入。</p></div>
<div class="paragraph"><p>我们输入的文法的文件，每行是一条对应文法的产生式，可以有空行，每个文法符号
用空格隔开，一段连续的字符串就是一个文法符号。</p></div>
<div class="paragraph"><p>对于正规文法我们扩充了文法，允许产生式右部第一个文法符号为仅推出终结符的
非终结符以减少文法长度。</p></div>
<div class="sect2">
<h3 id="_文法符号定义">文法符号定义</h3>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">文法符号第一个字符</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table">!</p></td>
<td align="left" valign="top"><p class="table">文法开始符</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table">$</p></td>
<td align="left" valign="top"><p class="table">非终结符</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table">@</p></td>
<td align="left" valign="top"><p class="table">词法分析器识别的非终结符</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table">其他</p></td>
<td align="left" valign="top"><p class="table">终结符</p></td>
</tr>
</tbody>
</table>
</div>
<div style="page-break-after:always"></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_整体架构">整体架构</h2>
<div class="sectionbody">
<div class="paragraph"><p>先由二型文法和三型文法初始化好相应的dfa，
整个语法分析过程由语法分析器的 <code>parse::lr_set_dfa::parse()</code> 不断调用词法分析器
的 <code>lex::dfa::lex()</code> ， <code>lex()</code> 每次返回一个token对，作为语法分析器的输入流
不断进行LR(1)分析。</p></div>
<div class="sect2">
<h3 id="_项目目录结构">项目目录结构</h3>
<div class="paragraph"><p>项目主要内容的目录结构如下：</p></div>
<div class="listingblock">
<div class="title">tree</div>
<div class="content">
<pre><code>.
├── readme.asciidoc
├── input-program
├── 2-grammar
├── 3-grammar
├── doc
│   ├── input-syntax
│   └── minipas
├── output-graph
│   ├── dfa-out.dot
│   ├── dfa.png
│   ├── nfa-out.dot
│   └── nfa.png
├── src
│   ├── parse.cc
│   ├── parse.hh
│   ├── pasex.cc
│   └── pasex.hh
├── main
├── main.cc</code></pre>
</div></div>
<div style="page-break-after:always"></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_词法分析器_pasex">词法分析器 pasex</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_词法所需结构体">词法所需结构体</h3>
<div class="paragraph"><p>首先看下词法分析器里定义的所有结构。</p></div>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">结构名称</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lex::symbol</code></p></td>
<td align="left" valign="top"><p class="table">文法符号</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lex::regular_rule</code></p></td>
<td align="left" valign="top"><p class="table">正则产生式</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lex::regular_grammar</code></p></td>
<td align="left" valign="top"><p class="table">正则文法</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lex::nfa::nfa</code></p></td>
<td align="left" valign="top"><p class="table">不确定有限状态机</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lex::dfa::dfa</code></p></td>
<td align="left" valign="top"><p class="table">确定有限状态机</p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p>我们重点介绍下nfa和dfa。</p></div>
</div>
<div class="sect2">
<h3 id="_nfa">nfa</h3>
<div class="sect3">
<h4 id="_nfa接口声明">nfa接口声明</h4>
<div class="paragraph"><p>我们来看下nfa里主要的接口。</p></div>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">函数声明</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>nfa(regular_grammar const &amp; g);</code></p></td>
<td align="left" valign="top"><p class="table">nfa构造函数，通过一个正则文法构造nfa</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>std::pair&lt;state, int&gt; closure(state const &amp; s) const;</code></p></td>
<td align="left" valign="top"><p class="table">返回一个nfa节点的epsilon闭包</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>state trans(state const &amp; s, char ch) const;</code></p></td>
<td align="left" valign="top"><p class="table">返回一个状态集经过一个字符转移后的状态集合</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>void add_edge(int u, int v, std::string const &amp; s);</code></p></td>
<td align="left" valign="top"><p class="table">在nfa上增加一条边</p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p>nfa的构造过程比较简单，对于形如 <code>$A-&gt;a $B</code> 只需要从 <code>$A</code> 的节点连向 <code>$B</code> 节点
一条标为 <code>a</code> 的边， 如果是形如 <code>$A-&gt;a</code> 的需要连一条从 <code>$A</code> 节点到终态节点为 <code>a</code> 的边，
形如 <code>$A-&gt;epsilon</code> 的只需要将节点 <code>$A</code> 标为终态。</p></div>
<div class="paragraph"><p>假如说我们要是别的是 <code>@identifier</code> 和 <code>@keyword</code> 两个状态，那么我们最终的nfa
是类似 (<code>@identifier</code> | <code>@keyword</code>)* 这么一条正则产生式所对应的nfa，所以我们
用正则产生式产生nfa的方法时给它隐含的加入了一个开始符，通过epsilon边连向这些
要识别的状态。还需要注意的是对于标记为要是别状态的节点，需要在终态节点上维护
相应是别状态的标记(flag)。</p></div>
</div>
<div class="sect3">
<h4 id="_nfa状态图">nfa状态图</h4>
<div class="paragraph"><p>这个是简化数字字母得到的nfa的状态图。</p></div>
<div class="imageblock">
<div class="content">
<img src="nfa.png" alt="NFA" width="1000" height="2000" />
</div>
<div class="title">Figure 1: NFA</div>
</div>
</div>
</div>
<div class="sect2">
<h3 id="_dfa">dfa</h3>
<div class="sect3">
<h4 id="_dfa接口声明">dfa接口声明</h4>
<div class="paragraph"><p>我们来看下dfa里主要的接口。</p></div>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">函数声明</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>dfa(nfa::nfa const &amp; n);</code></p></td>
<td align="left" valign="top"><p class="table">dfa构造函数，通过一个nfa构造nfa</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>token_type lex(std::string const &amp; str, std::string::iterator &amp; it);</code></p></td>
<td align="left" valign="top"><p class="table">返回从代码当前位置开始lex得到的一个token键值对</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>void add_edge(int u, int v, char ch);</code></p></td>
<td align="left" valign="top"><p class="table">在dfa上增加一条边</p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p>dfa的构造过程是一个bfs的过程，从nfa开始节点的闭包开始，枚举字母表向后转移
一个字符，然后得到一个nfa节点集合，再求这个集合的闭包，那么就可以从当前闭包
对应dfa的节点连一条转移字符的边到求得闭包对应的节点。</p></div>
<div class="paragraph"><p>lex是词法分析的主要过程，由语法分析器调用，一次调用返回程序当前位置开始得到的
一个token。</p></div>
</div>
<div class="sect3">
<h4 id="_dfa状态图">dfa状态图</h4>
<div class="paragraph"><p>这个是简化数字字母得到的确定化nfa后的dfa的状态图。</p></div>
<div class="imageblock">
<div class="content">
<img src="dfa.png" alt="DFA" width="1000" height="2000" />
</div>
<div class="title">Figure 2: DFA</div>
</div>
<div style="page-break-after:always"></div>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_语法分析器_parse">语法分析器 parse</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_语法分析所需结构体">语法分析所需结构体</h3>
<div class="paragraph"><p>首先看下语法分析器里定义的所有结构。</p></div>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">结构名称</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>parse::symbol</code></p></td>
<td align="left" valign="top"><p class="table">文法符号</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>parse::context_free_rule</code></p></td>
<td align="left" valign="top"><p class="table">上下文无关产生式</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>parse::context_free_grammar</code></p></td>
<td align="left" valign="top"><p class="table">上下文无关文法</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>parse::ex_context_free_rule</code></p></td>
<td align="left" valign="top"><p class="table">拓展的上下文无关产生式（增加点的位置）</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lr_set_base</code></p></td>
<td align="left" valign="top"><p class="table">LR项目集族的核心</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lr_set</code></p></td>
<td align="left" valign="top"><p class="table">LR项目集族</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lr_set_dfa</code></p></td>
<td align="left" valign="top"><p class="table">LR项目集族dfa</p></td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="sect2">
<h3 id="_lr项目集族dfa接口声明">LR项目集族dfa接口声明</h3>
<div class="paragraph"><p>我们重点介绍下LR项目集族dfa的接口。</p></div>
<div class="tableblock">
<table rules="all"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="50%" />
<col width="50%" />
<tbody>
<tr>
<td align="left" valign="top"><p class="table">函数声明</p></td>
<td align="left" valign="top"><p class="table">含义</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>lr_set_dfa(context_free_grammar const &amp; cfg)</code></p></td>
<td align="left" valign="top"><p class="table">lr_set_dfa构造函数，通过一个上下文无关文法构造dfa</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>bool acc(int state);</code></p></td>
<td align="left" valign="top"><p class="table">判断当前栈顶状态是不是acc状态</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>void add_edge(int u, int v, symbol const&amp; s);</code></p></td>
<td align="left" valign="top"><p class="table">在dfa上增加一条边</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>int rr_conflict_count() const;</code></p></td>
<td align="left" valign="top"><p class="table">dfa中有规约规约冲突的项目集族的个数</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>int sr_conflict_count() const;</code></p></td>
<td align="left" valign="top"><p class="table">dfa中有移进规约冲突的项目集族的个数</p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>bool parse(std::string const &amp; s, lex::dfa::dfa &amp; d);</code></p></td>
<td align="left" valign="top"><p class="table">语法分析的主过程，进行parse</p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p>LR项目集族dfa的构造函数如下：</p></div>
<div class="listingblock">
<a id="app-listing"></a>
<div class="content"><!-- Generator: GNU source-highlight 3.1.8
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite -->
<pre><tt>lr_set_dfa<span style="color: #990000">::</span><span style="font-weight: bold"><span style="color: #000000">lr_set_dfa</span></span><span style="color: #990000">(</span><span style="color: #008080">context_free_grammar</span> <span style="font-weight: bold"><span style="color: #0000FF">const</span></span> <span style="color: #990000">&amp;</span> cfg<span style="color: #990000">)</span>
<span style="color: #FF0000">{</span>
        <span style="color: #008080">context_free_rule</span> <span style="font-weight: bold"><span style="color: #000000">cfr</span></span><span style="color: #990000">(</span>cfg<span style="color: #990000">.</span>start_ex<span style="color: #990000">,</span> <span style="color: #FF0000">{</span>cfg<span style="color: #990000">.</span>start<span style="color: #FF0000">}</span><span style="color: #990000">);</span>
        <span style="color: #008080">lr_set_base</span> lsb<span style="color: #990000">;</span>
        lsb<span style="color: #990000">.</span><span style="font-weight: bold"><span style="color: #000000">add</span></span><span style="color: #990000">(</span><span style="font-weight: bold"><span style="color: #000000">ex_context_free_rule</span></span><span style="color: #990000">(</span>cfr<span style="color: #990000">,</span> <span style="color: #993399">0</span><span style="color: #990000">),</span> <span style="font-weight: bold"><span style="color: #000000">symbol</span></span><span style="color: #990000">(</span><span style="color: #FF0000">"#"</span><span style="color: #990000">));</span>
        <span style="font-weight: bold"><span style="color: #000000">node_index</span></span><span style="color: #990000">(</span><span style="font-weight: bold"><span style="color: #000000">lr_set</span></span><span style="color: #990000">(</span>lsb<span style="color: #990000">,</span> cfg<span style="color: #990000">));</span>
        <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> <span style="color: #990000">(</span><span style="color: #009900">int</span> i <span style="color: #990000">=</span> <span style="color: #993399">0</span><span style="color: #990000">;</span> i <span style="color: #990000">&lt;</span> <span style="color: #990000">(</span><span style="color: #009900">int</span><span style="color: #990000">)</span>all<span style="color: #990000">.</span><span style="font-weight: bold"><span style="color: #000000">size</span></span><span style="color: #990000">();</span> i<span style="color: #990000">++)</span> <span style="color: #FF0000">{</span>
                <span style="color: #009900">int</span> id <span style="color: #990000">=</span> <span style="font-weight: bold"><span style="color: #000000">node_index</span></span><span style="color: #990000">(</span>all<span style="color: #990000">[</span>i<span style="color: #990000">]);</span>
                std<span style="color: #990000">::</span><span style="color: #008080">map&lt;symbol, lr_set_base&gt;</span> tmp<span style="color: #990000">;</span>
                <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> <span style="color: #990000">(</span><span style="font-weight: bold"><span style="color: #0000FF">auto</span></span> ls <span style="color: #990000">:</span> all<span style="color: #990000">[</span>i<span style="color: #990000">].</span>lrs<span style="color: #990000">)</span> <span style="color: #FF0000">{</span>
                        <span style="font-weight: bold"><span style="color: #0000FF">if</span></span> <span style="color: #990000">(</span>ls<span style="color: #990000">.</span>first<span style="color: #990000">.</span>point <span style="color: #990000">==</span> <span style="color: #990000">(</span><span style="color: #009900">int</span><span style="color: #990000">)</span>ls<span style="color: #990000">.</span>first<span style="color: #990000">.</span>r<span style="color: #990000">.</span>rhs<span style="color: #990000">.</span><span style="font-weight: bold"><span style="color: #000000">size</span></span><span style="color: #990000">())</span> <span style="font-weight: bold"><span style="color: #0000FF">continue</span></span><span style="color: #990000">;</span>
                        <span style="font-weight: bold"><span style="color: #0000FF">auto</span></span> tt <span style="color: #990000">=</span> ls<span style="color: #990000">.</span>first<span style="color: #990000">;</span>
                        tt<span style="color: #990000">.</span>point<span style="color: #990000">++;</span>
                        tmp<span style="color: #990000">[</span>ls<span style="color: #990000">.</span>first<span style="color: #990000">.</span>r<span style="color: #990000">.</span>rhs<span style="color: #990000">[</span>ls<span style="color: #990000">.</span>first<span style="color: #990000">.</span>point<span style="color: #990000">]].</span><span style="font-weight: bold"><span style="color: #000000">add</span></span><span style="color: #990000">(</span>tt<span style="color: #990000">,</span> ls<span style="color: #990000">.</span>second<span style="color: #990000">);</span>
                <span style="color: #FF0000">}</span>
                <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> <span style="color: #990000">(</span><span style="font-weight: bold"><span style="color: #0000FF">auto</span></span> i <span style="color: #990000">:</span> tmp<span style="color: #990000">)</span>
                        <span style="font-weight: bold"><span style="color: #000000">add_edge</span></span><span style="color: #990000">(</span>id<span style="color: #990000">,</span> <span style="font-weight: bold"><span style="color: #000000">node_index</span></span><span style="color: #990000">(</span><span style="font-weight: bold"><span style="color: #000000">lr_set</span></span><span style="color: #990000">(</span>i<span style="color: #990000">.</span>second<span style="color: #990000">,</span> cfg<span style="color: #990000">)),</span> i<span style="color: #990000">.</span>first<span style="color: #990000">);</span>
        <span style="color: #FF0000">}</span>
<span style="color: #FF0000">}</span></tt></pre></div></div>
<div class="paragraph"><p>首先通过扩充文法，求得该扩充产生式的LR项目集闭包，然后不断枚举当前dfa上节点，
每次枚举项目集族中的产生式，如果是规约式就跳过，然后对于移进相同文法符号的
产生式通过 <code>std::map</code> 合并，得到LR项目集的核心，然后求该核心的闭包，就可以得到
两个节点的编号，然后就能通过 <code>add_edge</code> 函数给dfa加一条边。</p></div>
<div class="paragraph"><p>语法分析过程维护两个栈，状态栈和符号栈，在dfa上根据当前调用lex得到的文法符号
来决定是往下移动还是规约。如果有出边就移动到相应状态上，当前状态入栈以及文法符号
入栈，如果当前文法符号在某个可规约式的前向搜索符里，就可以进行规约, 然后状态会退，
再把规约后得到的文法符号入栈，移到相应状态上。最后如果在acc状态就是成功编译。
其他情况就会报错并停止。</p></div>
<div style="page-break-after:always"></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_使用实例">使用实例</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_词法分析">词法分析</h3>
<div class="paragraph"><p>我们用词法分析分析下面这段pascal代码：</p></div>
<div class="listingblock">
<a id="app-listing"></a>
<div class="content"><!-- Generator: GNU source-highlight 3.1.8
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite -->
<pre><tt><span style="font-weight: bold"><span style="color: #0000FF">var</span></span>     da<span style="color: #990000">:</span><span style="font-weight: bold"><span style="color: #0000FF">array</span></span><span style="color: #990000">[</span><span style="color: #993399">0</span><span style="color: #990000">..</span><span style="color: #993399">1000</span><span style="color: #990000">]</span><span style="font-weight: bold"><span style="color: #0000FF">of</span></span> longint<span style="color: #990000">;</span>
        d2<span style="color: #990000">:</span><span style="font-weight: bold"><span style="color: #0000FF">array</span></span><span style="color: #990000">[</span><span style="color: #993399">0</span><span style="color: #990000">..</span><span style="color: #993399">16</span><span style="color: #990000">]</span><span style="font-weight: bold"><span style="color: #0000FF">of</span></span> longint<span style="color: #990000">;</span>
        i<span style="color: #990000">,</span>j<span style="color: #990000">,</span>n<span style="color: #990000">,</span>m<span style="color: #990000">,</span>k<span style="color: #990000">,</span>d<span style="color: #990000">,</span>n2<span style="color: #990000">,</span>x<span style="color: #990000">,</span>s<span style="color: #990000">,</span>ans<span style="color: #990000">,</span>max<span style="color: #990000">,</span>t<span style="color: #990000">,</span>kk<span style="color: #990000">:</span>longint<span style="color: #990000">;</span>
<span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
        <span style="font-weight: bold"><span style="color: #0000FF">readln</span></span><span style="color: #990000">(</span>n<span style="color: #990000">,</span>d<span style="color: #990000">,</span>k<span style="color: #990000">);</span>
        d2<span style="color: #990000">[</span><span style="color: #993399">0</span><span style="color: #990000">]:=</span><span style="color: #993399">1</span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> i<span style="color: #990000">:=</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">to</span></span> d<span style="color: #990000">+</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">do</span></span> d2<span style="color: #990000">[</span>i<span style="color: #990000">]:=</span>d2<span style="color: #990000">[</span>i<span style="color: #990000">-</span><span style="color: #993399">1</span><span style="color: #990000">]*</span><span style="color: #993399">2</span><span style="color: #990000">;</span>

        <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> i<span style="color: #990000">:=</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">to</span></span> n <span style="font-weight: bold"><span style="color: #0000FF">do</span></span>
        <span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
                <span style="font-weight: bold"><span style="color: #0000FF">read</span></span><span style="color: #990000">(</span>m<span style="color: #990000">);</span>
                <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> j<span style="color: #990000">:=</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">to</span></span> m <span style="font-weight: bold"><span style="color: #0000FF">do</span></span>
                <span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
                        <span style="font-weight: bold"><span style="color: #0000FF">read</span></span><span style="color: #990000">(</span>s<span style="color: #990000">);</span>
                        da<span style="color: #990000">[</span>i<span style="color: #990000">]:=</span>da<span style="color: #990000">[</span>i<span style="color: #990000">]+</span>d2<span style="color: #990000">[</span>s<span style="color: #990000">-</span><span style="color: #993399">1</span><span style="color: #990000">];</span>
                <span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">;</span>
        n2<span style="color: #990000">:=</span>d2<span style="color: #990000">[</span>d<span style="color: #990000">];</span> max<span style="color: #990000">:=</span><span style="color: #993399">0</span><span style="color: #990000">;</span> t<span style="color: #990000">:=</span><span style="color: #993399">0</span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">writeln</span></span><span style="color: #990000">(</span>max<span style="color: #990000">);</span>
<span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">.</span></tt></pre></div></div>
<div class="sect3">
<h4 id="_输出token表">输出token表</h4>
<div class="paragraph"><p>将 <code>main.cc</code> 中的 <code>ALL_TOKEN</code> 宏开关设置成1我们得到结果运行如下：</p></div>
<div class="literalblock">
<div class="content">
<pre><code>token table:
@keyword                var
@delimiter              ^
@identifier             da
@delimiter              :
@keyword                array
@operator               [
@integer-literal        0
@delimiter              ..
@integer-literal        1000
@operator               ]
@keyword                of
@delimiter              ^
@type-identifier        longint
@delimiter              ;
@delimiter              ^
@identifier             d2
@delimiter              :
@keyword                array
@operator               [
@integer-literal        0
@delimiter              ..
@integer-literal        16
@operator               ]
@keyword                of
@delimiter              ^
@type-identifier        longint
@delimiter              ;
@delimiter              ^
@identifier             i
@delimiter              ,
@identifier             j
@delimiter              ,
@identifier             n
@delimiter              ,
@identifier             m
@delimiter              ,
@identifier             k
@delimiter              ,
@identifier             d
@delimiter              ,
@identifier             n2
@delimiter              ,
@identifier             x
@delimiter              ,
@identifier             s
@delimiter              ,
@identifier             ans
@delimiter              ,
@identifier             max
@delimiter              ,
@identifier             t
@delimiter              ,
@identifier             kk
@delimiter              :
@type-identifier        longint
@delimiter              ;
@delimiter              ^
@keyword                begin
@delimiter              ^
@keyword                readln
@operator               (
@identifier             n
@delimiter              ,
@identifier             d
@delimiter              ,
@identifier             k
@operator               )
@delimiter              ;
@delimiter              ^
@identifier             d2
@operator               [
@integer-literal        0
@operator               ]
@operator               :=
@integer-literal        1
@delimiter              ;
@delimiter              ^
@keyword                for
@delimiter              ^
@identifier             i
@operator               :=
@integer-literal        1
@delimiter              ^
@keyword                to
@delimiter              ^
@identifier             d
@operator               +
@integer-literal        1
@delimiter              ^
@keyword                do
@delimiter              ^
@identifier             d2
@operator               [
@identifier             i
@operator               ]
@operator               :=
@identifier             d2
@operator               [
@identifier             i
@operator               -
@integer-literal        1
@operator               ]
@operator               *
@integer-literal        2
@delimiter              ;
@delimiter              ^
@keyword                for
@delimiter              ^
@identifier             i
@operator               :=
@integer-literal        1
@delimiter              ^
@keyword                to
@delimiter              ^
@identifier             n
@delimiter              ^
@keyword                do
@delimiter              ^
@keyword                begin
@delimiter              ^
@keyword                read
@operator               (
@identifier             m
@operator               )
@delimiter              ;
@delimiter              ^
@keyword                for
@delimiter              ^
@identifier             j
@operator               :=
@integer-literal        1
@delimiter              ^
@keyword                to
@delimiter              ^
@identifier             m
@delimiter              ^
@keyword                do
@delimiter              ^
@keyword                begin
@delimiter              ^
@keyword                read
@operator               (
@identifier             s
@operator               )
@delimiter              ;
@delimiter              ^
@identifier             da
@operator               [
@identifier             i
@operator               ]
@operator               :=
@identifier             da
@operator               [
@identifier             i
@operator               ]
@operator               +
@identifier             d2
@operator               [
@identifier             s
@operator               -
@integer-literal        1
@operator               ]
@delimiter              ;
@delimiter              ^
@keyword                end
@delimiter              ;
@delimiter              ^
@keyword                end
@delimiter              ;
@delimiter              ^
@identifier             n2
@operator               :=
@identifier             d2
@operator               [
@identifier             d
@operator               ]
@delimiter              ;
@delimiter              ^
@identifier             max
@operator               :=
@integer-literal        0
@delimiter              ;
@delimiter              ^
@identifier             t
@operator               :=
@integer-literal        0
@delimiter              ;
@delimiter              ^
@keyword                writeln
@operator               (
@identifier             max
@operator               )
@delimiter              ;
@delimiter              ^
@keyword                end
@delimiter              .</code></pre>
</div></div>
<div class="paragraph"><p>其中 <code>^</code> 表示的空白符。</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_语法分析器">语法分析器</h3>
<div class="paragraph"><p>还是上面的代码, 我们将 <code>main.cc</code> 中的 <code>PARSE</code> 宏开关设置成1我们得到结果运行如下：</p></div>
<div class="literalblock">
<div class="content">
<pre><code>[ OK ] no error occured.</code></pre>
</div></div>
<div class="paragraph"><p>得到了一个通过语法分析的反馈。</p></div>
<div class="paragraph"><p>如果我们分析下面这段错误的代码：</p></div>
<div class="listingblock">
<a id="app-listing"></a>
<div class="content"><!-- Generator: GNU source-highlight 3.1.8
by Lorenzo Bettini
http://www.lorenzobettini.it
http://www.gnu.org/software/src-highlite -->
<pre><tt><span style="font-weight: bold"><span style="color: #0000FF">var</span></span>     da<span style="color: #990000">:</span><span style="font-weight: bold"><span style="color: #0000FF">array</span></span><span style="color: #990000">[</span><span style="color: #993399">0</span><span style="color: #990000">..</span><span style="color: #993399">1000</span><span style="color: #990000">]</span><span style="font-weight: bold"><span style="color: #0000FF">of</span></span> longint<span style="color: #990000">;</span>
<span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
                d1<span style="color: #990000">:=</span><span style="color: #FF0000">"123"</span><span style="color: #990000">;</span>
                d2<span style="color: #990000">:=</span><span style="color: #FF0000">"\"\\"</span><span style="color: #990000">;</span>
                d3<span style="color: #990000">:=</span><span style="color: #993399">123.3123e-123</span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">readln</span></span><span style="color: #990000">(</span>n<span style="color: #990000">,</span>d<span style="color: #990000">,</span>k<span style="color: #990000">);</span>

        <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> i<span style="color: #990000">:=</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">to</span></span> n <span style="font-weight: bold"><span style="color: #0000FF">do</span></span>
        <span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
                <span style="font-weight: bold"><span style="color: #0000FF">read</span></span><span style="color: #990000">(</span>m<span style="color: #990000">);</span>
                <span style="font-weight: bold"><span style="color: #0000FF">for</span></span> j<span style="color: #990000">:=</span><span style="color: #993399">1</span> <span style="font-weight: bold"><span style="color: #0000FF">to</span></span> m <span style="font-weight: bold"><span style="color: #0000FF">do</span></span>
                <span style="font-weight: bold"><span style="color: #0000FF">begin</span></span>
                        <span style="font-weight: bold"><span style="color: #0000FF">read</span></span><span style="color: #990000">(</span>s<span style="color: #990000">);</span>
                        da<span style="color: #990000">[</span>i<span style="color: #990000">]:=</span>da<span style="color: #990000">[</span>i<span style="color: #990000">]+</span>d2<span style="color: #990000">[</span>s<span style="color: #990000">-</span><span style="color: #993399">1</span><span style="color: #990000">];</span>
                <span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">;</span>
        <span style="font-weight: bold"><span style="color: #0000FF">writeln</span></span><span style="color: #990000">(</span>max<span style="color: #990000">);</span>
                <span style="font-weight: bold"><span style="color: #000000">wroteln</span></span><span style="color: #990000">(</span>max<span style="color: #990000">);</span>
<span style="font-weight: bold"><span style="color: #0000FF">end</span></span><span style="color: #990000">.</span></tt></pre></div></div>
<div class="paragraph"><p>如果打开语法分析中的 <code>ENABLE_DEBUG</code> 开关，就可以看到token流停止在</p></div>
<div class="literalblock">
<div class="content">
<pre><code>@identifier             wroteln
@operator               (</code></pre>
</div></div>
<div class="paragraph"><p>并且输出了 <code>[FAIL] some errors occured.</code> 表示语法分析出错。</p></div>
</div>
</div>
</div>
</div>
<div id="footnotes"><hr /></div>
<div id="footer">
<div id="footer-text">
Last updated 2016-05-24 14:21:15 CST
</div>
</div>
</body>
</html>
